import java.util.Deque;
import java.util.LinkedList;

/**
 * 239. 滑动窗口最大值
 * https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
 */
class Solution2 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length, cur = 0;
        int[] ret = new int[n - k + 1];
        MyDeque deque = new MyDeque();
        for(int i = 0; i < n; i++) {
            deque.push(nums[i]);
            if(i >= k - 1) {
                //取出此时的最大值
                ret[cur++] = deque.getMax();
                //取出最大值后要出队列
                deque.poll(nums[i + 1 - k]);
            }
        }
        return ret;
    }

}

//单调队列
class MyDeque {
    Deque<Integer> deque = new LinkedList<>();
    //进队列
    void push(int val) {
        //进队列前要判断前面元素是否有比val小的，如果有，那就弹出
        while(!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        //处理完上面情况，才能入队列
        deque.addLast(val);
    }
    //出队列
    void poll(int val) {
        //出队列时，判断出队列的元素是否为队头元素，如果是才弹出
        if(!deque.isEmpty() && val == deque.getFirst()) {
            deque.poll();
        }
    }
    //返回最大值
    int getMax() {
        //队顶元素始终是最大值
        return deque.peek();
    }
}